package com.demo.leetcode;

/**
 * 合并两个有序链表
 */
public class leetcode21 {

    /**
     * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * <p>
     * 示例：
     * 输入：1->2->4, 1->3->4
     * 输出：1->1->2->3->4->4
     */
    public static  Node mergeNode(Node node1, Node node2) {
        if (node1 == null) {
            return node2;
        }
        if (node2 == null) {
            return node1;
        }
        if (node1.val < node2.val) {
            node1.next = mergeNode(node1.next, node2);
            return node1;
        } else {
            node2.next = mergeNode(node1, node2.next);
            return node2;
        }
    }

    public static void main(String[] args) {
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        a.next = b;
        b.next = c;


        Node d = new Node(1);
        Node e = new Node(3);
        Node f = new Node(4);
        d.next = e;
        e.next = f;

        Node node = mergeNode(a, d);
        while (node!=null){
            System.out.println(node.val);
            node=node.next;
        }

    }


    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }
}
